Load-balancing networks are generally deployed for exchanging traffic between networks in a manner for handling dynamic traffic loads. In a load-balancing network, only ingress traffic speeds entering the load-balancing network and egress traffic speeds leaving the load-balancing network are known (i.e., the exact traffic between nodes of the load-balancing network are unknown). As such, since load-balancing networks generally distribute traffic load equally over the load-balancing network, all possible traffic matrices may be supported. In general, a given load for a network of N nodes may be expressed as an N×N traffic matrix, where each traffic matrix entry (row i, column j) defines the traffic load from one node (node i) to another node (node j).
In general, a load-balancing network operates according to a load-balancing algorithm subject to a set of constraints collectively known as the hose constraint. A traffic matrix meeting the hose constraint is considered a valid traffic matrix. In general, the hose constraint requires that: (1) the sum of the columns of the N×N matrix, for any row i, does not exceed the agreed ingress traffic rate at node i, and (2) the sum of the rows of the N×N matrix, for any column j, does not exceed the agreed egress traffic rate at node i. While limiting ingress traffic such that the hose constraint is satisfied is simple (e.g., setting ingress link capacity to provide a hard limit on ingress load or using a policer for maintaining the ingress load below ingress link capacity), limiting egress traffic such that the hose constraint is satisfied is difficult.
The limiting of egress traffic such that the hose constraint is satisfied may be achieving using various existing solutions. For example, limiting of egress traffic may be achieved using token bucket egress policing (without buffers), leaky bucket egress policing (having buffers)), or setting link speeds equal to the egress hose constraint. Disadvantageously, however, the token bucket solution results in Transmission Control Protocol (TCP) throughput reductions, and the leaky bucket and link speed solutions result in queuing and, therefore, additional delay in response to hose constraint violations. Furthermore, for each of these existing solutions (i.e., token bucket, leaky bucket, and link speed solutions), bandwidth may be wasted.
Furthermore, difficulty in limiting egress traffic for satisfying the hose constraint is primarily caused by the fact that nodes are not aware of the traffic load received by other nodes. Moreover, this difficulty may be exacerbated by certain services. For example, for broadcast services, one packet sent from an ingress node to an intermediate node may be replicated at the intermediate node. This replication results in an increase in egress traffic load, typically resulting in a violation of the hose constraint if there is insufficient egress capacity to support the increased egress load. Furthermore, when several services (from different customers) share an egress link and one of the services violates the hose constraint, the other services experience service performance degradation.